#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include "../base.hpp"

class MapGenerator
{
public:
    int minMapSize, maxMapSize;
    int minBlockNum, maxBlockNum;
    int minBoxNum, maxBoxNum;
    int RndPullStep;

    std::vector<std::vector<bool>> map;
    std::vector<std::vector<bool>> reachableArea;
    std::vector<Point2D> target;
    std::vector<Point2D> boxes;
    Point2D man;

    MapGenerator()
    {
        minMapSize = 4 + 2;
        maxMapSize = 8 + 2;
        minBlockNum = 2;
        maxBlockNum = maxMapSize * maxMapSize/2;
        minBoxNum = 2;
        maxBoxNum = 8;
        RndPullStep = 20;
        srand((unsigned int)time(NULL));
    }

    _State GenerateMap()
    {
        // cout << "check point 1" << endl;
        vector<Point2D> dire = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int mapSizeW = getRandom(minMapSize, maxMapSize);
        int mapSizeH = getRandom(minMapSize, maxMapSize);
        _State state;
        // 初始化地图
        state.map.clear();
        for (int i = 0; i < mapSizeH; i++)
        {
            vector<bool> tmp;
            for (int j = 0; j < mapSizeW; j++)
                tmp.push_back(false);
            state.map.push_back(tmp);
        }
        cout << "map size = " << mapSizeW << "," << mapSizeH << endl;
        // cout << "check point 2" << endl;

        // 确保外围是墙
        for (int i = 0; i < mapSizeW; i++)
        {
            state.map[0][i] = true;
            state.map[mapSizeH - 1][i] = true;
        }
        for (int i = 0; i < mapSizeH; i++)
        {
            state.map[i][0] = true;
            state.map[i][mapSizeW - 1] = true;
        }

        // cout << "check point 3" << endl;
        // 开始生成s
        cout << "Start to generate the map." << endl;
        int count = 0;
        // cin >> count;
        do
        {
            cout << "Try to Generate -- " << ++count << endl;
            // 初始化
            map = state.map;
            generateWall();
            initReachableArea();
            cout << "Testing reach ability." << endl;
            // 处理连通性
            bool flag = false;
            for (int i = 1; i < mapSizeH - 1; i++)
            {
                for (int j = 1; j < mapSizeW - 1; j++)
                {
                    if (!state.map[i][j])
                    {
                        flood((Point2D){j, i}, false);
                        flag = true;
                    }
                    if (flag)
                        break;
                }
                if (flag)
                    break;
            }

            // 如果不是全通的就重新生成
            if (!isAllReachable())
                continue;
            // 确定箱子的位置
            generateTarget();
            boxes = target;

            // 确定人的位置
            flag = false;
            for (int i = 1; i < mapSizeH - 1; i++)
            {
                for (int j = 1; j < mapSizeW - 1; j++)
                {
                    if (!map[i][j])
                    {
                        man = (Point2D){j, i};
                        flag = true;
                        for (int k = 0; k < boxes.size(); k++)
                            if (man == boxes[k])
                                flag = false;
                    }
                    if (flag)
                        break;
                }
                if (flag)
                    break;
            }

            // 拉箱子
            cout << "Pulling the boxes." << endl;
            for (int i = 0; i < RndPullStep; i++)
            {
                for (int j = 0; j < boxes.size(); j++)
                {
                    // printSense();
                    // 更新可达区域
                    initReachableArea();
                    flood(man, true);
                    // 寻找可执行操作
                    vector<Point2D> choice;
                    for (Point2D d : dire)
                        if (isPullAble(j, d.x, d.y))
                            choice.push_back(d);
                    if(choice.size() == 0)
                        continue;
                    Point2D d = choice[getRandom(0, choice.size() - 1)];
                    // 更新箱子和人的位置
                    boxes[j].x += d.x;
                    boxes[j].y += d.y;
                    man.x = boxes[j].x + d.x;
                    man.y = boxes[j].y + d.y;
                }
            }

            // 检查箱子的位置，如果箱子的位置都距离目标点太近就重新生成
            cout << "Checking the boxes." << endl;
            int maxDistance = 0;
            for (int i = 0; i < boxes.size(); i++)
            {
                int minDistance = mapSizeH + mapSizeW;
                for (int j = 0; j < target.size(); j++)
                {
                    int distance = abs(boxes[i].x - target[j].x) + abs(boxes[i].y - target[j].y);
                    if (distance < minDistance)
                        minDistance = distance;
                }
                if (minDistance > maxDistance)
                    maxDistance = minDistance;
            }
            if (maxDistance > 2)
                break;
        } while (1);

        cout << "Generate the map successfully." << endl;
        // 复制生成的地图状态到成员变量，用于绘图或其他用途
        state.map = map;
        state.man = man;
        state.step = 0;
        state.box = boxes;
        state.target = target;

        return state;
    }

    int getRandom(int min, int max)
    {
        return rand() % (max - min + 1) + min;
    }

    void generateWall()
    {
        int wallNum = getRandom(minBlockNum, maxBlockNum);
        for (int i = 0; i < wallNum; i++)
        {
            Point2D wallPos;
            wallPos.x = getRandom(1, map[0].size() - 2);
            wallPos.y = getRandom(1, map.size() - 2);
            // cout << "WallPoint: ( " << wallPos.x << " , " << wallPos.y << " )" << endl;
            map[wallPos.y][wallPos.x] = true;
        }
    }

    void printSense()
    {
        cout << endl;
        for (int i = 0; i < map.size(); i++)
        {
            for (int j = 0; j < map[0].size(); j++)
            {
                int flag = 0;
                for (int k = 0; k < boxes.size(); k++)
                    if (boxes[k] == (Point2D){j, i})
                        flag = 1;

                for (int k = 0; k < target.size(); k++)
                    if (target[k] == (Point2D){j, i})
                    {
                        if (flag == 1)
                            flag = 2;
                        else
                            flag = 3;
                    }

                if (flag == 1)
                    cout << "BB";
                else if (flag == 2)
                    cout << "bb";
                else if (flag == 3)
                    cout << "XX";
                else if (map[i][j])
                    cout << "WW";
                else
                    cout << "  ";
            }
            cout << endl;
        }
    }

    void generateTarget()
    {
        target.clear();
        int n = 0;
        int targetNum = getRandom(minBoxNum, maxBoxNum);

        for (int i = 0; i < map.size(); ++i)
        {
            for (int j = 0; j < map[0].size(); ++j)
            {
                if (!map[i][j])
                {
                    n++;
                }
            }
        }
        for (int i = 0; i < map.size(); ++i)
        {
            for (int j = 0; j < map[0].size(); ++j)
            {
                if (!map[i][j])
                {
                    if (getRandom(0, n) < targetNum) // t/n的概率
                        target.push_back(Point2D{j, i});
                    if (target.size() >= targetNum)
                        return;
                }
            }
        }
    }

    bool isAllReachable()
    {
        for (int i = 0; i < reachableArea.size(); ++i)
        {
            for (int j = 0; j < reachableArea[0].size(); ++j)
            {
                if (!reachableArea[i][j] && map[i][j] == false)
                {
                    return false;
                }
            }
        }
        return true;
    }

    bool isPullAble(int boxIndex, int dx, int dy)
    {
        Point2D box = boxes[boxIndex];
        Point2D newPos = {box.x + dx, box.y + dy};
        Point2D checkPos = {box.x + 2 * dx, box.y + 2 * dy};

        if (newPos.x < 0 || newPos.x >= map[0].size() || newPos.y < 0 || newPos.y >= map.size())
            return false;
        if (checkPos.x < 0 || checkPos.x >= map[0].size() || checkPos.y < 0 || checkPos.y >= map.size())
            return false;
        if (!reachableArea[newPos.y][newPos.x] || map[newPos.y][newPos.x])
            return false;
        if (!reachableArea[checkPos.y][checkPos.x] || map[checkPos.y][checkPos.x])
            return false;

        return true;
    }

    void initReachableArea()
    {
        reachableArea = map;
        for (int i = 0; i < reachableArea.size(); i++)
        {
            for (int j = 0; j < reachableArea[0].size(); j++)
                reachableArea[i][j] = false;
        }
    }

    void flood(Point2D start, bool ifCheckBox)
    {
        if (reachableArea[start.y][start.x] || map[start.y][start.x])
            return;
        if (ifCheckBox)
            for (int i = 0; i < boxes.size(); i++)
                if (boxes[i] == start)
                    return;

        reachableArea[start.y][start.x] = true;

        // 上下左右递归
        Point2D next = {start.x + 1, start.y};
        if (map[0].size() > next.x && !reachableArea[next.y][next.x])
            flood(next, ifCheckBox);

        next = {start.x - 1, start.y};
        if (0 < next.x && !reachableArea[next.y][next.x])
            flood(next, ifCheckBox);

        next = {start.x, start.y + 1};
        if (map.size() > next.y && !reachableArea[next.y][next.x])
            flood(next, ifCheckBox);

        next = {start.x, start.y - 1};
        if (0 < next.y && !reachableArea[next.y][next.x])
            flood(next, ifCheckBox);
    }
};
